/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-19 11:04:24
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-20 10:01:27
 * @FilePath: \LeetCode\101.对称二叉树.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=101 lang=cpp
 *
 * [101] 对称二叉树
 *
 * 方法1：递归判断 - 左右子树使用不同的遍历顺序
 *
 * 方法2：迭代判断 - 对称访问左右子树
 */

#include <stack>
#include <queue>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// @lc code=start

class Solution
{
public:
    std::queue<TreeNode *> leftNodes;

    void insertLeft(TreeNode *root) // 将左子树插入 queue
    {
        /* 根 - 左 - 右 */
        if (root == nullptr)
        {
            leftNodes.push(nullptr);
            return;
        }
        else
            leftNodes.push(root);
        insertLeft(root->left);
        insertLeft(root->right);
    }

    bool compareRight(TreeNode *root)
    {
        /* 根 - 右 - 左 */
        if ((root == nullptr && leftNodes.front() == nullptr) ||
            (root != nullptr && leftNodes.front() != nullptr && root->val == leftNodes.front()->val))
            leftNodes.pop();
        else
            return false;

        if (root == nullptr)
            return true;
        return compareRight(root->right) && compareRight(root->left);
    }

    bool isSymmetric(TreeNode *root)
    {
        std::stack<TreeNode *> leftTree, rightTree;
        if (root->left != nullptr)
            leftTree.push(root->left);
        if (root->right != nullptr)
            rightTree.push(root->right);

        while (!leftTree.empty() && !rightTree.empty())
        {
            TreeNode *leftNode = leftTree.top();
            leftTree.pop();
            TreeNode *rightNode = rightTree.top();
            rightTree.pop();

            if (leftNode == nullptr && rightNode == nullptr)
                continue;
            else if (leftNode == nullptr || rightNode == nullptr)
                return false;

            if (leftNode->val != rightNode->val)
                return false;
            /* 左子树：根 - 左 - 右 */
            leftTree.push(leftNode->left);
            leftTree.push(leftNode->right);
            /* 右子树：根 - 右 - 左 */
            rightTree.push(rightNode->right);
            rightTree.push(rightNode->left);
        }

        return (leftTree.empty() && rightTree.empty());
    }
};
// @lc code=end
